1. Field of the Invention
This invention relates to an error correction system which detects and corrects errors in a storage medium, such as an optical disk, a magnetic disk or the like, or in a communication channel of satellite communications or the like, utilizing error correcting codes.
2. Description of the Prior Art
Recently, error correcting codes have been utilized more and more as means for increasing reliability in various kinds of digital systems, such as in a memory system using optical disks or the like. Among various kinds of error correcting codes which have the same code length and correcting capability, a Reed-Solomon code (hereinafter termed an "RS code") is the most important from the viewpoint of practical use, because it includes the feature of providing the smallest redundancy. Accordingly, the RS code has been widely utilized in satellite communications, optical disks, magnetic disks or the like.
An encoder/decoder or a decoder for performing processing of the RS code at a high speed may be relatively easily provided if the correcting capability of the RS code is as small as about 1 or 2.
However, if the correcting capability is increased, the size and control of the device becomes very complicated, and the calculation time needed for decoding processing is also increased.
In order to solve the above-described problems, an error correction method using systolic arrays, which is one of many parallel processing methods, has been proposed (e.g., the Transactions of the Institute of Electronics, Information and Communication Engineers, Vol. J71-A, No. 3, pp. 751-759, referred to as the IEICE Article, and which generally corresponds to copending U.S. patent application, Ser. No. 07/982,062).
According to this method, high-speed processing can be realized with a simple control and a simple circuit configuration for a code having a large correcting capability by performing all the processing necessary for encoding/decoding using the RS code with a configuration of systolic arrays having the same processing elements (hereinafter referred to as "PEs").
An example of the system configuration using the conventional systolic array configuration is shown in FIG. 7. An example of the circuit configuration of the PEs is shown in FIG. 8.
In this method, as shown in FIG. 7, a series of processing steps necessary for encoding/decoding using an RS code are performed in a sequential pipeline system using processing units 1-6 comprising the same PEs each having, for example, the configuration shown in FIG. 8.
In FIG. 8, there are shown a selector 11 controlled by signals S1 and S2, multipliers 12 and 13 on a Galois field, an adder 14 on a Galois field, and registers 15-19.
However, the conventional processing system, wherein all the processing necessary for encoding/decoding using the RS code is performed using the configuration of the systolic arrays having the same PEs, has a problem that respective processing units have different frequencies, that is, calculation loads, necessary for one processing step due to differences in the contents of the respective processing steps, such as the generation of a syndrome polynomial, the generation of an error locator polynomial or the like.
That is, when trying to perform all the processing steps necessary for encoding using the RS code by the systolic arrays, units which await processing are present within the system during the execution of the processing, because the calculation load differs for each processing unit. Hence, the overall system is not very efficient.
When correcting an erasure, a case may occur wherein the number "s" of erasures is "0" (no erasure is present) according to a codeword. In such a case, in the conventional method, (d-2t-1) PEs are always allocated for the generation of an erasure locator polynomial, where d represents a minimum distance and t represents the correcting capability). Hence, a delay time is needed for such an allocation.